|
In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856〔(The Largest Known Prime by Year: A Brief History )〕 and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s. ==The test== The Lucas–Lehmer test works as follows. Let ''M''''p'' = 2''p'' − 1 be the Mersenne number to test with ''p'' an odd prime. The primality of ''p'' can be efficiently checked with a simple algorithm like trial division since ''p'' is exponentially smaller than ''M''''p''. Define a sequence for all ''i'' ≥ 0 by : The first few terms of this sequence are 4, 14, 194, 37634, ... . Then ''M''''p'' is prime if and only if : The number ''s''''p'' − 2 mod ''M''''p'' is called the Lucas–Lehmer residue of ''p''. (Some authors equivalently set ''s''1 = 4 and test ''s''''p''−1 mod ''M''''p''). In pseudocode, the test might be written as ''// Determine if M''p'' = 2''p'' − 1 is prime Lucas–Lehmer(p) var s = 4 var M = 2''p'' − 1 repeat p − 2 times: s = ((s × s) − 2) mod M if s = 0 return PRIME else return COMPOSITE Performing the mod M at each iteration ensures that all intermediate results are at most ''p'' bits (otherwise the number of bits would double each iteration). The same strategy is used in modular exponentiation.抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lucas–Lehmer primality test」の詳細全文を読む スポンサード リンク
|